1. Field of the Invention
The present invention relates to a code error detecting apparatus for detecting the occurrence or non-occurrence of a code error by performing the communication or data processing of the digital data. More specifically, the present invention relates to a CRC operational calculating method and a CRC operational calculation circuit for generating a CRC (Cyclic Redundancy Check) to perform error detection and correction for received data in a digital communication system.
2. Discussion of the Background Art
In a CRC calculating method and CRC calculation circuit, LSI is typically utilized. The method and circuit have an operational calculating function for calculating a cyclic redundancy check code for detecting the occurrence or non-occurrence of a code error by performing the communication or data processing of the digital data.
High-speed performance of CRC calculation in connection with error detection has been strictly (strongly) required in accordance with the high-speed performance requirements of data communication.
One such background-art CRC calculation circuit aimed at responding to the requirement of high-speed CRC calculation, for instance, is disclosed in the published specification of Japanese Laid-open Patent Publication No. 6-37,737/1994. Hereinafter, the technology relating to the calculation circuit described in this publication will be referred to as xe2x80x9cthe first background-art technologyxe2x80x9d.
FIG. 3 is a circuit diagram for explaining the CRC calculation circuit of the first background-art technology.
The first background-art CRC calculation circuit includes: n-stage storing circuits 11 connected to each other through the respective corresponding first through (nxe2x88x921)-th exclusive logical sum circuits 14 and for storing the result of the CRC calculation by the n-order creating multinomial equation. A recurrence symbol selecting circuit 12 selects one of the recurrence code signals from among the first through n-th storing circuit outputs of the n-th hereby certify that this paper is being deposited this date with the storing circuits 11 in accordance with the first through n-th coefficient input signal of the CRC creating multinomial equation. An n-th exclusive logical sum circuit 14 performs an exclusive logical sum of the input binary signal and the recurrence code signal output both for calculating the CRC, and for inputting the output signal thereof to the first storing circuit 11 of the n-stage storing circuits. The first through (nxe2x88x921)-th logical sum circuits 15 respectively take the logical sum of the output signal of the n-th exclusive logical sum circuit and the first through (nxe2x88x921)-th coefficient input signals, and respectively input the output signals thereof to the corresponding first through (nxe2x88x921)-th exclusive logical sum circuits.
In the CRC calculation circuit of such structure, by enabling the coefficient of the CRC creating multinomial equation to be optionally set, when changing-over of the CRC creating multinomial equation is required, it is not necessary to prepare the CRC calculation circuits corresponding to the number (sort) of the required CRC creating multinomial equations.
Furthermore, it is described in the background-art document that only one CRC calculating circuit is sufficient and therefore the size of the circuit can be made small. In addition, even when the coefficient of the required CRC creating multinomial equation has to be changed, it is sufficient to only change the setting thereof. Therefore, it is possible to easily change the setting of the coefficient.
Another type of background-art CRC calculation circuit, for instance, is described in the published specification of Japanese Laid-open Patent Publication No. 9-69,836/1997. Hereinafter, the technology concerning the type of calculation circuit described in this publication is referred to as xe2x80x9cthe second background-art technologyxe2x80x9d.
FIG. 4 is a circuit diagram for explaining the CRC calculation circuit of the second background-art technology.
In FIG. 4, the second background-art CRC calculation circuit performs division of the information data input in parallel with the previously determined paralleling rate by use of a predetermined CRC creating multinomial equation. By obtaining the surplus (residue) of the division, the CRC code can be created as the error detecting (cyclic) redundancy code for the information data.
The surplus can be obtained by dividing the number of bits of the information data by the paralleling rate. The information data attached with xe2x80x9cOxe2x80x9d of the same number as that of the value obtained by subtracting the surplus from the parallel rate is multiplied by the monomial equation including the order number of the value obtained as the result of performing the modulo calculation with the period of the CRC creating multinomial equation in connection with the value obtained by subtracting the number of xe2x80x9cOxe2x80x9d attached to the information data from the number of bits of the CRC code. Thereafter the division is performed by use of the CRC creating multinomial equation, by use of an operational calculation medium. The CRC code generating circuit includes the operational calculation medium for performing such division and the outputting medium for outputting the surplus obtained by the division performed by the above-mentioned operational calculation medium as the CRC code for the information data.
The above background-art document (second background art) describes that, in such structure of the CRC calculation circuit, even though the bit number of the information data can be indivisible (cannot be divided) by the paralleling rate of the CRC calculation, the CRC code creating circuit can be effectively realized.
The document further describes that the paralleling rate of the information input to the calculation circuit need not be changed and nevertheless it is possible to form the structure the same as that of the background-art CRC creating method with very small time delay, and the CRC code can be created without increasing the scale of the circuit (size, number of parts, etc.) and with the time delay as small as possible compared with the background-art circuit structure in which the number of bits of the information data is a multiple of the paralleling rate.
Another type of CRC calculation circuit, for instance, is described in the published specification of Japanese Laid-open Patent Publication No. 6-224,783/1994. The technology concerning this type of circuit is called hereinafter xe2x80x9cthe third background-art technologyxe2x80x9d.
FIG. 5 is a circuit diagram for explaining the CRC calculation circuit of the third background-art technology.
In FIG. 5, a CRC calculation circuit performs a cyclic coding process and a cyclic redundant code check (CRC) process both for data of a number predetermined by the m-order creating multinomial equation G(X) (m is an integer satisfying mxe2x89xa6n/2) by use of a computer provided with a n-bit commonly used register. The CRC calculation circuit according to the third background-art technology is composed of CPU 100a, a table ROM 200, a data memory 300 and a bus 400. Table ROM 200 stores a surplus table for storing 2n surplus tables created by surplus data obtained by dividing the respective 2n data by the CRC creating multinomial equation. A reference address creating medium generates a reference address of the surplus table. A surplus table reading-out medium reads out the surplus table corresponding to the reference address. A repetition medium repeats a predetermined number of times the reference address creating medium and the surplus table reading-out medium.
Here, when the surplus table satisfies n/2xe2x88x92m=0 for the respective 2n data {Dn} [{Dn}={d0, d1, d2, . . . , dnxe2x88x921 }, di (i is an integer, on the condition of 0xe2x89xa6ixe2x89xa6nxe2x88x921) is 0 or 1, K is an integer on the condition of 0xe2x89xa6Kxe2x89xa62n], one of the data created by the modulo-2 division of dividing the data multinomial equation D(X) of the equation 1 drawn out from the data {Dn} by the CRC creating multinomial equation G(X) is composed of 2n surplus data of xc2xd bit. On the contrary, when the surplus table satisfies n/2 xe2x88x92m greater than 0 for the data {Dn}, the data {d0, d1, d2, . . . , dn/2xe2x88x92m+1} are respectively added to the surplus data {r0, r1, r2, . . . , rmxe2x88x921} obtained as the result of the modulo-2 division of dividing the data multinomial equation Da(X) of the equation 2 from the (n/2+m)-th bit by the CRC creating multinomial equation G(X). One of the data thus created is composed of 2n data of one bit {d0, d1, d2, . . . , dn/2xe2x88x92m+1, r0, r1, r2, . . . , rmxe2x88x921.
Furthermore, the reference address creating medium creates the first reference address in accordance with the first data which is the n-th bit from the head of the data of the predetermined number. The medium further creates the second reference address by connecting the upper-column N/2 bit data of the first surplus table which are read out at the time of creating the first reference address to the lower-column w/2 bit data of the first data.
In such structure of the CRC calculating circuit, by preparing the surplus table previously storing the 2n upper-column table, the processings of shifting and composing can be made possible per each of the n/2 bits. Therefore, the time consumed for the cyclic coding process and the CRC process can be shortened, and the computer can be effectively utilized for the many other processings such as the control of the communication protocol, etc. Moreover, it is not necessary to prepare a high-speed computer for shortening the processing time. The above-mentioned merits are also described in the same document.
Yet another type of CRC calculation circuit, for instance, is disclosed is the published specification of Japanese Laid-open Patent Publication No. 6-311,049/1994. The technology concerning this type of circuit is called hereinafter xe2x80x9cthe fourth background-art technologyxe2x80x9d.
FIG. 6 is a circuit diagram for explaining the fourth background-art CRC calculation circuit.
In FIG. 6, the fourth background-art CRC calculating circuit is composed of four D-type flip-flops 20 for inputting in parallel the data to be measured per four bits, and sixteen D-type flip-flops 22 (X0xcx9cX15), the respective outputs of which are connected to the CRC code outputs. A first exclusive logical sum circuit 24 calculates the exclusive logical sums (W, X, Y, Z) of the upper four columns (X12xcx9cX15) output from the sixteen D-type flip-flops 22 and the outputs of the four D-type flip-flops 20 (D0xcx9cD3). A second exclusive logical sum circuit 26 calculates the exclusive logical sums (a, b, c, d) of the subsequent upper four columns (X8xcx9cX11) outputs of the sixteen D-type flip-flops 22 and the outputs (W, X, Y, Z) of the first exclusive logical sum circuit 24. A third exclusive logical sum circuit 28 calculates the exclusive logical sums (e, f, g, h) of the outputs of the lower four columns (X1xcx9cX4) of the sixteen D-type flip-flops 22 excluding the lowermost column and the outputs (W, X, Y, Z) of the first exclusive logical sum circuit 24.
The fourth background-art CRC calculating circuit is constructed such that the outputs (W, X, Y, Z) of the first exclusive logical sum circuit 24 are respectively connected to the inputs the lower four D-type flip-flops 22 (X0xcx9cX3). The outputs (h, g, f, e) of the third exclusive logical sum circuit 28 respectively are input to the D-type flip-flops 22 (X5xcx9cX8). The outputs of D-type flip-flops 22 (X5xcx9cX7) are connected respectively to flip-flop inputs X9xcx9cX11, and the outputs (d, c, b, a) of the second exclusive logical sum circuit are connected respectively to the inputs of flip-flops 22 (X12xcx9cX15).
In the fourth background-art CRC calculating circuit, the data input circuit inputs in parallel the data to be calculated per four bits, and the first exclusive logical sum circuit 24 calculates the exclusive logical sums W, X, Y, Z by adding the four bits to the upper four columns X12xcx9cX15 of the sixteen D-type flip-flops X0xcx9cX15 connected to the CRC code output of the CRC code outputting circuit.
Next, the second exclusive logical sum circuit 26 calculates the exclusive logical sums a, b, c, d by adding the subsequent upper four columns X8xcx9cX11 output from the sixteen D-type flip-flops 22 and the outputs W, X, Y, Z of the first exclusive logical sum circuit 24. At the same time, the third exclusive logical sum circuit 28 calculates the exclusive logical sum of the outputs of the lower four columns X1xcx9cX4 excluding the lowermost column of the sixteen D-type flip-flops X0xcx9cX15 and the outputs W, X, Y, Z of the first exclusive logical sum circuit 24.
The respective data are inputted to the input terminals of the sixteen D-type flip-flops X0xcx9cX15. Namely, the outputs W, X, Y, Z of the first exclusive logical sum circuit 24 are respectively connected to X0xcx9cX3 in the order from the lower column and to the inputs of X0 to X4. The outputs h, g, f, e of the third exclusive logical sum circuit 28 are connected respectively to X5xcx9cX8. The outputs of X5xcx9cX7 are connected respectively to the inputs of X9xcx9cX11, and the outputs a, b, c, d of circuit 26 are connected respectively to the inputs of X12xcx9cX15. The above background-art document describes such structure and function as mentioned above.
The same document further describes that, in such structure of the CRC calculation circuit, the processings for creating the CRC code can be simplified and the speed thereof can be raised, by processing the input data per four bits, and furthermore, even in the case of realizing such circuit with software, the coding and decoding of the CRC can be processed with high speed by use of the programming technology.
In the CRC calculation circuits of the first and second background-art technologies, it is easy, in principle, to change the position of the exclusive logical sum gate (XOR gate) situated between the shift registers. Although some merit can be found from the viewpoint of industrial utilization, when a shift register is employed, a data transmission process of only one bit per clock is performed. Consequently, it is necessary to perform the clock shift at least eight times in order to calculate the CRC16xc2x70 for the usually used octet data (eight bits), and therefore such CRC calculation circuit is not in conformity with (not fit for) high-speed performance. Those matters as mentioned heretofore are the problems to be solved.
Furthermore, regarding the CRC calculation circuit of the third background-art CRC calculation circuit, the calculation result of the cyclic redundancy check is previously stored in the surplus table storing medium (more specifically, system memory ROM) and the necessary value of the CRC calculation can be obtained in such circuit structure by referring to the table. The apparatus (circuit) as mentioned above is well known. However, in such apparatus, the capacity of the system memory is limited. In addition, the apparatus is not optimized for industrial utilization in consideration of the system cycle required for the number subtracting calculation for referring to the memory. These matters as mentioned above are also problems to be solved.
Furthermore, regarding the CRC calculation circuit of the fourth background-art CRC calculation circuit, although the processing for four bits with one clock can be performed and thereby the processing time can be shortened, at least two clocks need to be used in order to obtain the desired CRC calculation value, and thereby it is necessary to previously divide the octet data (eight bits) as the value to be calculated into four bits. Therefore, it is necessary to separately prepare outside the hardware or the software a pre-processing system. These matters are also problems to be solved.
The present invention was made in order to solve the above-mentioned problems.
In the present invention, it is possible to utilize LSI having an operational calculating function for calculating the CRC creating multinomial equation:
G(X)=X16+X12+X5+1
in order to calculate the CRC code which is described in ITUxe2x80x94T [International Telecommunication Unionxe2x80x94Telecommunication Sector CCITT (Consultative Committee of International Telephone and Telegraph)] Recommendation.
It is an object of the present invention to solve the background-art defects such as the above-mentioned problems.
It is another object of the present invention to provide a CRC operational calculating method and a CRC operational calculation circuit solving the background-art defects such as the above-mentioned problems.
It is still another object of the present invention to provide a CRC operational calculating method and a CRC operational calculation circuit capable of realizing the calculation of the cyclic redundancy check by use of only a combination of logic circuits.
It is still another object of the present invention to provide a CRC operational calculating method and a CRC operational calculation circuit capable of realizing calculation of the cyclic redundancy check by use of only a combination of logic circuits such as gate circuits, and thereby enable the completion of the calculation within one clock cycle.